/*-------------------------------------------------------------------------
 *
 * spgquadtreeproc.c
 *	  四叉树在 SP-GiST 中的实现
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/spgist/spgquadtreeproc.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/spgist.h"
#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/float.h"
#include "utils/geo_decls.h"

Datum spg_quad_config(PG_FUNCTION_ARGS)
{
	/* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
	spgConfigOut *fc_cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

	fc_cfg->prefixType = POINTOID;
	fc_cfg->labelType = VOIDOID;	/* 我们不需要节点标签 */
	fc_cfg->canReturnData = true;
	fc_cfg->longValuesOK = false;
	PG_RETURN_VOID();
}

#define SPTEST(f, x, y) \
	DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))

/* 报告所有节点都应该被访问 */
/* 使用父象限框作为 traversalValue */
/* “which” 是满足所有约束的象限的位掩码 */
/*
				 * 对于这个操作符，查询是一个框而不是一个点。
				 * 我们在此假设 DatumGetPointP 不会对指向框的指针
				 * 执行任何有害的操作。
				 */
static int16 fc_getQuadrant(Point *fc_centroid, Point *fc_tst)
{
	if ((SPTEST(point_above, fc_tst, fc_centroid) ||
		 SPTEST(point_horiz, fc_tst, fc_centroid)) &&
		(SPTEST(point_right, fc_tst, fc_centroid) ||
		 SPTEST(point_vert, fc_tst, fc_centroid)))
		return 1;

	if (SPTEST(point_below, fc_tst, fc_centroid) &&
		(SPTEST(point_right, fc_tst, fc_centroid) ||
		 SPTEST(point_vert, fc_tst, fc_centroid)))
		return 2;

	if ((SPTEST(point_below, fc_tst, fc_centroid) ||
		 SPTEST(point_horiz, fc_tst, fc_centroid)) &&
		SPTEST(point_left, fc_tst, fc_centroid))
		return 3;

	if (SPTEST(point_above, fc_tst, fc_centroid) &&
		SPTEST(point_left, fc_tst, fc_centroid))
		return 4;

	elog(ERROR, "getQuadrant: impossible case");
	return 0;
}

/* 质心在框内，因此所有象限都是可以的 */
/* 确定包含框所有角点的象限 */
/* 无需考虑剩余条件 */
/* 我们必须进入由 which 确定的象限 */
/* 所有测试都是精确的 */
/* leafDatum 就是它本来的样子... */
/* 执行所需的比较 */
/*
				 * 对于这个操作符，查询是一个框而不是一个点。
				 * 我们在此假设 DatumGetPointP 不会对指向框的指针
				 * 执行任何有害的操作。
				 */
static BOX *
fc_getQuadrantArea(BOX *fc_bbox, Point *fc_centroid, int fc_quadrant)
{
	BOX		   *fc_result = (BOX *) palloc(sizeof(BOX));

	switch (fc_quadrant)
	{
		case 1:
			fc_result->high = fc_bbox->high;
			fc_result->low = *fc_centroid;
			break;
		case 2:
			fc_result->high.x = fc_bbox->high.x;
			fc_result->high.y = fc_centroid->y;
			fc_result->low.x = fc_centroid->x;
			fc_result->low.y = fc_bbox->low.y;
			break;
		case 3:
			fc_result->high = *fc_centroid;
			fc_result->low = fc_bbox->low;
			break;
		case 4:
			fc_result->high.x = fc_centroid->x;
			fc_result->high.y = fc_bbox->high.y;
			fc_result->low.x = fc_bbox->low.x;
			fc_result->low.y = fc_centroid->y;
			break;
	}

	return fc_result;
}

Datum spg_quad_choose(PG_FUNCTION_ARGS)
{
	spgChooseIn *fc_in = (spgChooseIn *) PG_GETARG_POINTER(0);
	spgChooseOut *fc_out = (spgChooseOut *) PG_GETARG_POINTER(1);
	Point	   *fc_inPoint = DatumGetPointP(fc_in->datum),
			   *fc_centroid;

	if (fc_in->allTheSame)
	{
		fc_out->resultType = spgMatchNode;
		/* 好的，它通过了 -> 让我们计算距离 */
		fc_out->result.matchNode.levelAdd = 0;
		fc_out->result.matchNode.restDatum = PointPGetDatum(fc_inPoint);
		PG_RETURN_VOID();
	}

	Assert(fc_in->hasPrefix);
	fc_centroid = DatumGetPointP(fc_in->prefixDatum);

	Assert(fc_in->nNodes == 4);

	fc_out->resultType = spgMatchNode;
	fc_out->result.matchNode.nodeN = fc_getQuadrant(fc_centroid, fc_inPoint) - 1;
	fc_out->result.matchNode.levelAdd = 0;
	fc_out->result.matchNode.restDatum = PointPGetDatum(fc_inPoint);

	PG_RETURN_VOID();
}

#ifdef USE_MEDIAN
static int fc_x_cmp(const void *fc_a, const void *fc_b, void *fc_arg)
{
	Point	   *fc_pa = *(Point **) fc_a;
	Point	   *fc_pb = *(Point **) fc_b;

	if (fc_pa->x == fc_pb->x)
		return 0;
	return (fc_pa->x > fc_pb->x) ? 1 : -1;
}

static int fc_y_cmp(const void *fc_a, const void *fc_b, void *fc_arg)
{
	Point	   *fc_pa = *(Point **) fc_a;
	Point	   *fc_pb = *(Point **) fc_b;

	if (fc_pa->y == fc_pb->y)
		return 0;
	return (fc_pa->y > fc_pb->y) ? 1 : -1;
}
#endif

Datum spg_quad_picksplit(PG_FUNCTION_ARGS)
{
	spgPickSplitIn *fc_in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
	spgPickSplitOut *fc_out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
	int			fc_i;
	Point	   *fc_centroid;

#ifdef USE_MEDIAN
	/* Use the median values of x and y as the centroid point */
	Point	  **fc_sorted;

	fc_sorted = palloc(sizeof(*fc_sorted) * fc_in->nTuples);
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
		fc_sorted[fc_i] = DatumGetPointP(fc_in->datums[fc_i]);

	fc_centroid = palloc(sizeof(*fc_centroid));

	qsort(fc_sorted, fc_in->nTuples, sizeof(*fc_sorted), fc_x_cmp);
	fc_centroid->x = fc_sorted[fc_in->nTuples >> 1]->x;
	qsort(fc_sorted, fc_in->nTuples, sizeof(*fc_sorted), fc_y_cmp);
	fc_centroid->y = fc_sorted[fc_in->nTuples >> 1]->y;
#else
	/* Use the average values of x and y as the centroid point */
	fc_centroid = palloc0(sizeof(*fc_centroid));

	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		fc_centroid->x += DatumGetPointP(fc_in->datums[fc_i])->x;
		fc_centroid->y += DatumGetPointP(fc_in->datums[fc_i])->y;
	}

	fc_centroid->x /= fc_in->nTuples;
	fc_centroid->y /= fc_in->nTuples;
#endif

	fc_out->hasPrefix = true;
	fc_out->prefixDatum = PointPGetDatum(fc_centroid);

	fc_out->nNodes = 4;
	fc_out->nodeLabels = NULL;		/* 我们不需要节点标签 */

	fc_out->mapTuplesToNodes = palloc(sizeof(int) * fc_in->nTuples);
	fc_out->leafTupleDatums = palloc(sizeof(Datum) * fc_in->nTuples);

	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		Point	   *fc_p = DatumGetPointP(fc_in->datums[fc_i]);
		int			fc_quadrant = fc_getQuadrant(fc_centroid, fc_p) - 1;

		fc_out->leafTupleDatums[fc_i] = PointPGetDatum(fc_p);
		fc_out->mapTuplesToNodes[fc_i] = fc_quadrant;
	}

	PG_RETURN_VOID();
}


Datum spg_quad_inner_consistent(PG_FUNCTION_ARGS)
{
	spgInnerConsistentIn *fc_in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
	spgInnerConsistentOut *fc_out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
	Point	   *fc_centroid;
	BOX			fc_infbbox;
	BOX		   *fc_bbox = NULL;
	int			fc_which;
	int			fc_i;

	Assert(fc_in->hasPrefix);
	fc_centroid = DatumGetPointP(fc_in->prefixDatum);

	/*
	 * When ordering scan keys are specified, we've to calculate distance for
	 * them.  In order to do that, we need calculate bounding boxes for all
	 * children nodes.  Calculation of those bounding boxes on non-zero level
	 * require knowledge of bounding box of upper node.  So, we save bounding
	 * boxes to traversalValues.
	 */
	if (fc_in->norderbys > 0)
	{
		fc_out->distances = (double **) palloc(sizeof(double *) * fc_in->nNodes);
		fc_out->traversalValues = (void **) palloc(sizeof(void *) * fc_in->nNodes);

		if (fc_in->level == 0)
		{
			double		fc_inf = get_float8_infinity();

			fc_infbbox.high.x = fc_inf;
			fc_infbbox.high.y = fc_inf;
			fc_infbbox.low.x = -fc_inf;
			fc_infbbox.low.y = -fc_inf;
			fc_bbox = &fc_infbbox;
		}
		else
		{
			fc_bbox = fc_in->traversalValue;
			Assert(fc_bbox);
		}
	}

	if (fc_in->allTheSame)
	{
		/* Report that all nodes should be visited */
		fc_out->nNodes = fc_in->nNodes;
		fc_out->nodeNumbers = (int *) palloc(sizeof(int) * fc_in->nNodes);
		for (fc_i = 0; fc_i < fc_in->nNodes; fc_i++)
		{
			fc_out->nodeNumbers[fc_i] = fc_i;

			if (fc_in->norderbys > 0)
			{
				MemoryContext fc_oldCtx = MemoryContextSwitchTo(fc_in->traversalMemoryContext);

				/* Use parent quadrant box as traversalValue */
				BOX		   *fc_quadrant = box_copy(fc_bbox);

				MemoryContextSwitchTo(fc_oldCtx);

				fc_out->traversalValues[fc_i] = fc_quadrant;
				fc_out->distances[fc_i] = spg_key_orderbys_distances(BoxPGetDatum(fc_quadrant), false,
															   fc_in->orderbys, fc_in->norderbys);
			}
		}
		PG_RETURN_VOID();
	}

	Assert(fc_in->nNodes == 4);

	/* "which" is a bitmask of quadrants that satisfy all constraints */
	fc_which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);

	for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
	{
		Point	   *fc_query = DatumGetPointP(fc_in->scankeys[fc_i].sk_argument);
		BOX		   *fc_boxQuery;

		switch (fc_in->scankeys[fc_i].sk_strategy)
		{
			case RTLeftStrategyNumber:
				if (SPTEST(point_right, fc_centroid, fc_query))
					fc_which &= (1 << 3) | (1 << 4);
				break;
			case RTRightStrategyNumber:
				if (SPTEST(point_left, fc_centroid, fc_query))
					fc_which &= (1 << 1) | (1 << 2);
				break;
			case RTSameStrategyNumber:
				fc_which &= (1 << fc_getQuadrant(fc_centroid, fc_query));
				break;
			case RTBelowStrategyNumber:
			case RTOldBelowStrategyNumber:
				if (SPTEST(point_above, fc_centroid, fc_query))
					fc_which &= (1 << 2) | (1 << 3);
				break;
			case RTAboveStrategyNumber:
			case RTOldAboveStrategyNumber:
				if (SPTEST(point_below, fc_centroid, fc_query))
					fc_which &= (1 << 1) | (1 << 4);
				break;
			case RTContainedByStrategyNumber:

				/*
				 * 对于这个操作符，查询是一个盒子而不是一个点。我们在假设DatumGetPointP不会
				 * 对指向盒子的指针做任何不好的事情的程度上进行了一些作弊。
				 */
				fc_boxQuery = DatumGetBoxP(fc_in->scankeys[fc_i].sk_argument);

				if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
													 PointerGetDatum(fc_boxQuery),
													 PointerGetDatum(fc_centroid))))
				{
					/* centroid is in box, so all quadrants are OK */
				}
				else
				{
					/* identify quadrant(s) containing all corners of box */
					Point		fc_p;
					int			fc_r = 0;

					fc_p = fc_boxQuery->low;
					fc_r |= 1 << fc_getQuadrant(fc_centroid, &fc_p);
					fc_p.y = fc_boxQuery->high.y;
					fc_r |= 1 << fc_getQuadrant(fc_centroid, &fc_p);
					fc_p = fc_boxQuery->high;
					fc_r |= 1 << fc_getQuadrant(fc_centroid, &fc_p);
					fc_p.x = fc_boxQuery->low.x;
					fc_r |= 1 << fc_getQuadrant(fc_centroid, &fc_p);

					fc_which &= fc_r;
				}
				break;
			default:
				elog(ERROR, "unrecognized strategy number: %d",
					 fc_in->scankeys[fc_i].sk_strategy);
				break;
		}

		if (fc_which == 0)
			break;				/* 不需要考虑其余条件 */
	}

	fc_out->levelAdds = palloc(sizeof(int) * 4);
	for (fc_i = 0; fc_i < 4; ++fc_i)
		fc_out->levelAdds[fc_i] = 1;

	/* We must descend into the quadrant(s) identified by which */
	fc_out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
	fc_out->nNodes = 0;

	for (fc_i = 1; fc_i <= 4; fc_i++)
	{
		if (fc_which & (1 << fc_i))
		{
			fc_out->nodeNumbers[fc_out->nNodes] = fc_i - 1;

			if (fc_in->norderbys > 0)
			{
				MemoryContext fc_oldCtx = MemoryContextSwitchTo(fc_in->traversalMemoryContext);
				BOX		   *fc_quadrant = fc_getQuadrantArea(fc_bbox, fc_centroid, fc_i);

				MemoryContextSwitchTo(fc_oldCtx);

				fc_out->traversalValues[fc_out->nNodes] = fc_quadrant;

				fc_out->distances[fc_out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(fc_quadrant), false,
																		 fc_in->orderbys, fc_in->norderbys);
			}

			fc_out->nNodes++;
		}
	}

	PG_RETURN_VOID();
}


Datum spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
{
	spgLeafConsistentIn *fc_in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
	spgLeafConsistentOut *fc_out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
	Point	   *fc_datum = DatumGetPointP(fc_in->leafDatum);
	bool		fc_res;
	int			fc_i;

	/* 所有测试都是精确的 */
	fc_out->recheck = false;

	/* leafDatum is what it is... */
	fc_out->leafValue = fc_in->leafDatum;

	/* 执行所需的比较 */
	fc_res = true;
	for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
	{
		Point	   *fc_query = DatumGetPointP(fc_in->scankeys[fc_i].sk_argument);

		switch (fc_in->scankeys[fc_i].sk_strategy)
		{
			case RTLeftStrategyNumber:
				fc_res = SPTEST(point_left, fc_datum, fc_query);
				break;
			case RTRightStrategyNumber:
				fc_res = SPTEST(point_right, fc_datum, fc_query);
				break;
			case RTSameStrategyNumber:
				fc_res = SPTEST(point_eq, fc_datum, fc_query);
				break;
			case RTBelowStrategyNumber:
			case RTOldBelowStrategyNumber:
				fc_res = SPTEST(point_below, fc_datum, fc_query);
				break;
			case RTAboveStrategyNumber:
			case RTOldAboveStrategyNumber:
				fc_res = SPTEST(point_above, fc_datum, fc_query);
				break;
			case RTContainedByStrategyNumber:

				/*
				 * 对于这个操作符，查询是一个盒子而不是一个点。我们在假设DatumGetPointP不会
				 * 对指向盒子的指针做任何不好的事情的程度上进行了一些作弊。
				 */
				fc_res = SPTEST(box_contain_pt, fc_query, fc_datum);
				break;
			default:
				elog(ERROR, "unrecognized strategy number: %d",
					 fc_in->scankeys[fc_i].sk_strategy);
				break;
		}

		if (!fc_res)
			break;
	}

	if (fc_res && fc_in->norderbys > 0)
		/* ok, it passes -> let's compute the distances */
		fc_out->distances = spg_key_orderbys_distances(fc_in->leafDatum, true,
													fc_in->orderbys, fc_in->norderbys);

	PG_RETURN_BOOL(fc_res);
}
